package sort;

import java.util.Arrays;

/**
 * 基数排序
 */
public class RadixSort {

  public static void main(String[] args) {

    int[] array ={45,8,123,980,35,7,0,57,6,980,34,465,3,7,2,89};
    radixSort(array);
    System.out.println(Arrays.toString(array));
  }

  private static void radixSort(int[] array) {

    int max=array[0];
    for (int i = 1; i < array.length; i++) {
      if (array[i]>max){
        max=array[i];
      }
    }
    //找到数组中最大元素的位数
    int maxLength=(max+"").length();

    //十个桶，每个桶里面最多有maxLength个元素
    int[][] buckets = new int[10][array.length];
    //记录每个桶中已经装入元素的个数
    int[] bucketEleCont=new int[10];

    for (int i = 0 , n=1; i < maxLength; i++,n*=10) {

      for (int j=0;j<array.length;j++){
        //取出每个元素对应次数的值（个位，十位，百位....）
        int num=array[j] / n %10;

        //将元素放入索引为num的桶里面
        buckets[num][bucketEleCont[num]]=array[j];
        bucketEleCont[num]++;
      }

      int index = 0;//记录原数组的索引
      //依次将桶中数据取出放回原数组
      for (int k=0;k<bucketEleCont.length;k++){
        //对应的桶中有元素
        if (bucketEleCont[k]!=0){
          for (int m=0;m<bucketEleCont[k];m++){
            array[index]=buckets[k][m];
            index++;
          }
        }
        //每一轮将桶中元素的个数清零
        bucketEleCont[k]=0;
      }
    }
  }
}
